package solution


// 31. 下一个排列
// 给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
func Leecode31_nextPermutation(nums []int) {
	i := len(nums) - 2
	for i >= 0 && nums[i] > nums[i+1] {
		i--
	}
	if i>0 {
		j := len(nums) - 1
		for j>=0 && nums[i] >= nums[j] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	// reverse
	var reverse func(i, j int)
	reverse = func(start, end int) {
		for start < end {
			nums[start], nums[end] = nums[end], nums[start]
			start++
			end--
		}
	}
	reverse(i+1, len(nums)-1)
}
